In a conventional network interconnected through Ethernet bridges, because the same and unique spanning tree is adopted to forward data in the same broadcast domain, it generally cannot ensure that data packets are forwarded along the shortest path, and as a result, the data packets are intensely transmitted merely in some links. For example, as shown in FIG. 1, in the network interconnected through Ethernet bridges, A represents a root bridge, B and C are blocked, and so are C and D. Therefore, even though both B and D have straight links to C, data packets from B and D to C must be forwarded by A first and then reach C, so that the bandwidths between B and C, and C and D are wasted.
In order to enable a bridge to forward data packets along a shortest path, currently, the shortest path bridge project team of an International organization for Standardization IEEE (Institute for Electrical and Electronics Engineers) and the TRILL (Transparent Interconnection of Lots of Links) project team of an International organization for Standardization IETF (Internet Engineering Task Force) have respectively organized researches according to two different methods.
In the method adopted by the shortest path bridge project team of the IEEE, a spanning tree is still adopted to forward all the data packets. However, each bridge in the whole network acts as a root bridge to generate a tree, and establish their respective forwarding trees. In order to forward data packets, including broadcast packets, multicast packets, unknown packets, or unicast packets, along the shortest path, during the process of forwarding data packets, a first bridge where a data packet firstly arrives is taken as a root, and then the data is forwarded, according to a forwarding tree established by the bridge itself. In other words, the entrance is taken as the root to forward data. Therefore, according to the method, a plurality of spanning trees may be employed in the same broadcast domain to forward data.
In the method adopted by the TRILL project team of the IETF, a bridge has routing calculation and forwarding functions similar to a router. Therefore, the bridge in this method is also called a route bridge (Rbridge). Each Rbridge can form a “Rbridge network topology” based on a link-state protocol and, accordingly, calculate a shortest path to any other destination Rbridge. As for a unicast packet, each Rbridge can forward a unicast packet along the shortest path, according to the address of an exit Rbridge corresponding to the data packet (not based on the address of the final destination node, i.e. not based on the MAC address of a destination host). In addition, a network including Rbridges may calculate a spanning tree, according to the network topology, and broadcast packets, multicast packets, and unknown packets are all forwarded, according to the spanning tree.
In order to avoid significantly modifying the hardware through adding Time To Live (TTL) process in the loop, in the method adopted by the TRILL project team of the IETF the spanning tree is merely modified, which slightly affects the hardware changes. Therefore, at present, in the research on the shortest path bridge, the IEEE has proposed two solutions around the spanning tree.
1. A spanning tree is established by employing original spanning tree protocols: Rapid Spanning Tree Protocol and Multiple Spanning Tree Protocol (RSTP/MSTP). This solution is the focus of the current study made by the IEEE.
2. A spanning tree is established by employing Intermediate system-Intermediate system (IS-IS) or Open Shortest Path First Protocol (OSPF).
In Solution 2, after a spanning tree is established by the IS-IS, because each bridge knows the topology of the whole network, and the spanning tree established by each bridge includes the spanning trees of the whole network, each bridge knows the branch of the spanning tree where any node is located, and knows how to forward data, according to the established spanning tree.
In Solution 1, after a spanning tree is established by the spanning tree protocol, each bridge can only know a root port and a designated port of one spanning tree passing from the bridge, instead of the information about the whole spanning tree. Therefore, if a unicast packet is forwarded by taking an entrance as the root, each bridge does not know the branch of the spanning tree where a destination address accesses, so that the bridge obtains a forwarding path by address learning.
However, the spanning tree of each bridge is generated independently. When two or more equivalent paths exist, different spanning trees adopt different manners to block the equivalent paths when being generated independently, so that the path selections are inconsistent; and as a result, the forward and backward paths from one bridge to another are inconsistent. For example, in the network shown in FIG. 2, a path a (taking A as the tree root) from an edge bridge A to an edge bridge I is inconsistent with a path i (taking I as the tree root) from the edge bridge I to the edge bridge A. Therefore, the above forwarding mechanism taking an entrance as a root causes difficulties in address learning due to asymmetric paths; and as a result, a normal forwarding path cannot be obtained by a common source address learning method.
In order to overcome the learning obstacles caused by asymmetric paths in the above shortest path forwarding system taking an entrance as a root, in the conventional art, the IEEE proposes a symmetric path generation method of a PATH vector.
The basic principle for the symmetric path generation method of a PATH vector is to ensure that the path a from the edge bridge A to the edge bridge I is consistent with the path i from the edge bridge I to the edge bridge A. In order to implement the method, a N-bit PATH vector should be predetermined when establishing bridges through using MSTP, in which N cannot be less than the number of bridges in the network, and a fixed bit is assigned to each bridge.
In order to make the original MSTP protocol of the MSTP be compatible, designated Bridge ID in {Root ID, Root Path Cost, designated Bridge ID, Port ID} in a priority vector is replaced by a PATH vector, so the vector has 64 bits. In addition, an algorithm (or static configuration) is adopted in advance to ensure the costs of a link in forward and backward directions to be consistent.
In the above symmetric path generation method of a PATH vector, in the process of establishing multiple spanning trees, the PATH vector is created and propagated in the following manner.
Each bridge is taken as a tree root to initialize an empty PATH vector, and adds the PATH vector into a Bridge Protocol Data Unit (BPDU) message corresponding to the tree root for being propagated.
When a BPDU message carrying a PATH vector is propagated to a certain bridge, if the bridge determines that a port for receiving the BPDU message is a root port of the tree corresponding to the BPDU message according to a unique shortest root cost, and fills the position assigned thereto with 1 in the PATH vector contained in the BPDU message, locally stores the PATH vector, and then continues to propagate the BPDU message carrying the PATH vector to a non-root port. Otherwise, if the bridge calculates two shortest equivalent root costs of a corresponding tree, it carries out the following processes. Two PATH vectors corresponding to the two equivalent roots (the bit in the PATH vectors corresponding to the bridge is set as 1) are taken, and the path corresponding to one PATH vector is determined to be blocked, according to a specified rule. For example, the values of the two PATH vectors are respectively converted into a N-digit integer, and the vector with a larger value has its corresponding path blocked.
As shown in FIG. 3, when the BPDU rooted at A is transmitted to E, the bridge E marks the position in the PATH vector corresponding to E with 1, and transmits the newly-constructed BPDU to H and G from two different ports, respectively. When receiving the BPDU rooted at A, H marks the position in the PATH vector corresponding to H with 1. When receiving the BPDU rooted at A, G marks the position in the PATH vector corresponding to G with 1. In this way, each bridge marks the corresponding position in the vector with 1 after receiving the BPDU rooted at A. When B receives the BPDU rooted at A from two different paths, the PATH vector is shown in the first two rows in Table 1, and when E receives the BPDU rooted at I from two different paths, the PATH vector is shown in the last two rows in Table 1.
TABLE 1PathABCDEFGHIAEHCB111000010AEGDB110100100IBCHE011010011IBDGE010110101
The above method can ensure that, during the generation process of different spanning trees, when equivalent paths exist, the protocols of different spanning trees may determine the blocked paths, according to the two equivalent PATH vectors corresponding to the tree and the same blocking rule, thereby ensuring the consistency (symmetry) of forward and backward paths between two points, when using different spanning trees to forward data.
When implementing the present invention, the inventor finds out that the above symmetric path generation method of a PATH vector in the conventional art has the defects that, because the number of bits in the PATH vector is directly proportional to the network size, the number of bits in the PATH vector closely relates to the network scalability, so the method is inappropriate for the network scalability. For the compatibility of protocols, the current PATH vector is 64 bits, which obviously cannot satisfy the requirements of scalability.
In this method, the bit of each bridge needs to be allocated manually in advance, which means a heavy workload. In addition, once the bit allocated to a newly-added bridge in the network is made to be the same as that of another bridge by mistake, the two bridges with incorrect configurations can only be found out by searching all bridges one by one, and the whole network cannot be recovered automatically, thereby causing disastrous consequences to the whole network.
Under a special circumstance, two equivalent paths crossed the same bridge, but merely the ports are different. Such a problem may not be solved by this method. In addition, the method is only suitable for a point to point link, but still has the problem of path asymmetry in a multi-point access link.